package com.xj.algorithm.leetcode;

/**
 * 重复的子字符串
 */
public class L459_重复子串构成字符串 {

    /**
     * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "abab"
     * <p>
     * 输出: True
     * <p>
     * 解释: 可由子字符串 "ab" 重复两次构成。
     * 示例 2:
     * <p>
     * 输入: "aba"
     * <p>
     * 输出: False
     * 示例 3:
     * <p>
     * 输入: "abcabcabcabc"
     * <p>
     * 输出: True
     * <p>
     * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
     */
    public static void main(String[] args) {
        System.out.println(repeatedSubstringPattern("abab"));
        System.out.println(repeatedSubstringPattern("aba"));
        System.out.println(repeatedSubstringPattern("abcabcabcabc"));
        System.out.println(repeatedSubstringPattern("ababab"));
        System.out.println(repeatedSubstringPattern("aabaaba"));
        System.out.println(repeatedSubstringPattern("babbabbabbabbab"));

        System.out.println(repeatedSubstringPatternGood("babbabbabbabbab"));

    }

    //自己的解法：遍历，从1到长度的一半
    public static boolean repeatedSubstringPattern(String s) {
        int lenght = s.length();
        for (int i = lenght / 2; i > 0; i --) {
            if(lenght%i!=0){
                continue;
            }

            //截取字符串,范围是左闭右开[)
            String mark=s.substring(0,i);
            int nextLeft=i;
            int nextRight=nextLeft+i;
            boolean flag=true;
            while (nextRight<=lenght){
                String cmp=s.substring(nextLeft,nextRight);
                if(!mark.equals(cmp)){
                    flag=false;
                    break;
                }

                nextLeft=nextRight;
                nextRight=nextLeft+i;
            }
            if(flag==true){
                return true;
            }
        }
        return false;
    }

    //精彩解法：字符串叠加，找是否包含自己。滑动窗口
    public static boolean repeatedSubstringPatternGood(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);  //去头去尾后，是否包含自己
    }

}
